package NO6_Tree;

/**
 * 2025-08-15
 * 力扣 - 222. 完全二叉树的节点个数
 * <p>
 * 给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。
 * 完全二叉树 的定义如下：
 * 在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。
 * 若最底层为第 h 层（从第 0 层开始），则该层包含 1~ 2h 个节点。
 */
public class CountNodesMain {

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1,
                new TreeNode(2, new TreeNode(4), new TreeNode(5)),
                new TreeNode(3, new TreeNode(6), new TreeNode(7)));
        System.out.println(countNodes(root));
    }

    // 遍历递归
//    public static int countNodes(TreeNode root) {
//        if (root == null) return 0;
//        return 1 + countNodes(root.left) + countNodes(root.right);
//    }

    // 利用完全二叉树性质
    public static int countNodes(TreeNode root) {
        if (root == null) {
            return 0;
        }
        if (root.left == null && root.right == null) {
            return 1;
        }

        int leftHeight = getHeight(root.left);
        int rightHeight = getHeight(root.right);

        if (leftHeight == rightHeight) {
            // 左子树是满二叉树
            // 左子树节点数 = 2^leftHeight（用位运算替代）
            return (1 << leftHeight) + countNodes(root.right);
        } else {
            // 右子树是满二叉树（高度少1）
            return (1 << rightHeight) + countNodes(root.left);
        }
    }

    private static int getHeight(TreeNode root) {
        int height = 0;
        while (root != null) {
            height++;
            root = root.left; // 完全二叉树左子树决定高度
        }
        return height;
    }

}
